package com.cango.student.algorithm.sort;

/**
 * 快速排序
 * 时间复杂度（平均）	时间复杂度（最坏)	时间复杂度（最好)	空间复杂度	稳定性	复杂性
 * O(nlog2n) 	       O(n2)	      O(nlog2n)	    O(nlog2n)	不稳定	较复杂
 */
public class Quicksort {

    static int[] a = {40,9,20,4,30,1,54,6,8,99};
    static int n;

    public static void quicksort(int left,int right) {
        int i,j,t,temp;

        if(left>right)
            return;
        // temp中存的就是基准数
        temp=a[left];
        i=left;
        j=right;
        while(i!=j) {
            // 顺序很重要，要先从右边开始找
            while(a[j]>=temp && i<j)
                j--;
            // 再找右边的
            while(a[i]<=temp && i<j)
                i++;
            // 交换两个数在数组中的位置
            if(i<j) {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        // 最终将基准数归位
        a[left]=a[i];
        a[i]=temp;
        // 继续处理左边的，这里是一个递归的过程
        quicksort(left,i-1);
        // 继续处理右边的 ，这里是一个递归的过程
        quicksort(i+1,right);
    }

    public static void main(String[] args) {
        n = 9;

        for(int i=0;i<=n;i++)
            System.out.print(a[i] + " ");

        quicksort(0,n); //快速排序调用
        System.out.println("");
        //输出排序后的结果
        for(int i=0;i<=n;i++)
            System.out.print(a[i] + " ");
    }
}
